package book_mianshizhinan.test1_8;

import java.util.Stack;

public class MaxTree {

	public static void main(String[] args) {

		int[] arr = { 3, 4, 5, 1, 2 };
		Node root = MaxTree.getMaxTree(arr);
		System.out.println("root:"+root.value);
		syso(root);
	}

	public static void syso(Node root) {
		if(root == null){
			return;
		}
		syso(root.left);
		System.out.println(root.value);
		syso(root.right);
	}

	public static Node getMaxTree(int[] arr) {
		Node[] nNode = new Node[arr.length];
		for (int i = 0; i < arr.length; i++) {
			nNode[i] = new Node(arr[i]);
		}
		Stack<Integer> foo = new Stack<Integer>();
		int[] lmax = new int[arr.length];
		int[] rmax = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			while (!foo.isEmpty() && arr[foo.peek()] <= arr[i]) {
				foo.pop();
			}
			if (foo.isEmpty()) {
				lmax[i] = -1;
			} else {
				lmax[i] = foo.peek();
			}
			foo.push(i);
		}

		/*
		 * for (int i : lmax) { System.out.println(i); }
		 */

		foo.clear();
		for (int i = arr.length - 1; i >= 0; i--) {
			while (!foo.isEmpty() && arr[foo.peek()] <= arr[i]) {
				foo.pop();
			}
			if (foo.isEmpty()) {
				rmax[i] = -1;
			} else {
				rmax[i] = foo.peek();
			}
			foo.push(i);
		}

		/*for (int i : rmax) {
			System.out.println(i);
		}*/

		Node root = null;
		for (int i = 0; i < arr.length; i++) {
			if (lmax[i] == -1 && rmax[i] == -1) {// 找到根结点
				root = nNode[i];
			} else {
				//System.out.println(lmax[i] + ":" + rmax[i]);
				if (lmax[i] == -1) {
					nNode[rmax[i]].left = nNode[i];
					continue;
				}
				if (rmax[i] == -1) {
					nNode[lmax[i]].right = nNode[i];
					continue;
				}
				if (arr[lmax[i]] > arr[rmax[i]]) {
					nNode[rmax[i]].left = nNode[i];
				} else {
					nNode[lmax[i]].right = nNode[i];
				}
			}

		}

		return root;

	}

}
